package listbyorder.access001_100.test51;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/1 15:34
 */
public class Solution1 {

    // 经典回溯——一种比较简单的写法
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        // 进入回溯体
        dfs(res, new ArrayList<Integer>(), n);
        return res;
    }

    private void dfs(List<List<String>> res, ArrayList<Integer> path, int n) {
        if (path.size() == n) {
            // 当前的状态path已经安排好了所有的皇后，生成结果即可
            List<String> temp = new ArrayList<>();
            for (Integer site : path) {
                char[] t = new char[n];
                Arrays.fill(t, '.');
                t[site] = 'Q';
                temp.add(new String(t));
            }
            res.add(temp);
            return;
        }
        // 从第列遍历当前数组
        for (int i = 0; i < n; i++) {
            // 当前的列在之前的path中没有出现过，才会加入到当前的path
            if (!path.contains(i)) {
                // 判断当前是否满足对角线上的元素满足条件
                if (isXsite(path, i)) {
                    path.add(i);
                    dfs(res, path, n);
                    path.remove(path.size() - 1);
                }
            }
        }
    }

    // 这步是关键
    private boolean isXsite(ArrayList<Integer> path, int cur) {
        if (path == null) return true;
        int size = path.size();
        for (int i = 0; i < path.size(); i++) {
            if (Math.abs(cur - path.get(i)) == size - i) {
                return false;
            }
        }
        return true;
    }
}
